/**********************************************************************/
/**  Copyright (c) ECC labs. 2001-2002. All Rights Reserved.		 **/
/**********************************************************************/
/*
	bincode.cpp
	Mark Papazyan

*/


#include "binlongm.h"

void renew(CBinLongWord& a, int n){

	if(a.num)
		delete[] a.num;

	a.len=n/MOD;
	if(n!=a.len*MOD)
		a.len++;
	a.n=n;
	a.num=new t_src[a.len];

	for(t_cnt i=0; i<a.len; i++)
		a.num[i]=(t_src)0;
}


CBinLongMatrix::CBinLongMatrix(t_len k, t_len n, int flag, int base)
	:k(k),n(n),flag(flag), base(base)
{	
	row = new CBinLongWord[k];
	col = new CBinLongWord[n];

	for(t_cnt i=0; i<k; i++)
		renew(row[i], n);

	for(t_cnt l=0; l<n; l++)
		renew(col[l], k);

/*	if(flag & ROW)
		cur=row;
	else
		cur=col;
		*/
}




CBinLongMatrix::CBinLongMatrix(const CBinLongMatrix& t)
{
	row=new CBinLongWord[k=t.k];
	col=new CBinLongWord[n=t.n];

	flag=t.flag;
	base=t.base;

	for(t_cnt i=0; i<k; i++)
	{
		renew(row[i], n);
		for(t_cnt g=0; g<row[0].len; g++)
			row[i].num[g]=t.row[i].num[g];
	}
	
	for(t_cnt ii=0; ii<n; ii++)
		renew(col[ii], k);

	if(t.flag&HAVE_COL)//checks if cols were made
		for(t_cnt j=0; j<n; j++)
			for(t_cnt g=0; g<col[0].len; g++)
				col[j].num[g]=t.col[j].num[g];
}


CBinLongMatrix::~CBinLongMatrix()
{
	delete[] row;
	delete[] col;
}


ostream& operator<<(ostream& out, CBinLongMatrix& a)
{
	t_cnt i=0;
	if(a.flag & ROW)
	switch(a.base){
	 case BIN:
		for(i=0; i<a.k; i++)
			out<<a.row[i]<<'\n';
		break;
/*	 case HEX:
		for(i=0; i<a.k; i++)
			out<<"0x"<<hex<<(I)a.row[i].num<<'\n';
		break;
	 case OCT:
		 for(i=0; i<a.k; i++)
			out<<0<<oct<<(I)a.row[i].num<<'\n';
		break;
	 default:
		 for(i=0; i<a.k; i++)
			out<<(I)a.row[i].num<<'\n';*/
		}


	else if(a.flag&COL)
	 switch(a.base){
		 case BIN:
			for(i=0; i<a.n; i++)
				out<<a.col[i]<<'\n';
			break;
/*		 case HEX:
			for(i=0; i<a.n; i++)
				out<<"0x"<<hex<<(I)a.col[i].num<<'\n';
			break;
		 case OCT:
			 for(i=0; i<a.n; i++)
				out<<0<<oct<<(I)a.col[i].num<<'\n';
			break;
		 default:
			 for(i=0; i<a.n; i++)
				out<<(I)a.col[i].num<<'\n';*/
			}

	return out;
}




istream& operator>>(istream& in, CBinLongMatrix& a)
{
	t_cnt i=0;
	if(a.flag&ROW)
		for(i=0; i<a.k; i++)
			in>>a.row[i];

	else if(a.flag&COL)
		for(i=0; i<a.n; i++)
			in>>a.col[i];

	return in;
}


CBinLongMatrix& CBinLongMatrix::operator=(const CBinLongMatrix& t)
{
	if(this!=&t)
	{
		delete[] row;
		delete[] col;
		

		row=new CBinLongWord[k=t.k];
		col=new CBinLongWord[n=t.n];

		flag=t.flag;
		base=t.base;

		for(t_cnt i=0; i<k; i++)
		{
			renew(row[i], n);
			for(t_cnt g=0; g<row[0].len; g++)
				row[i].num[g]=t.row[i].num[g];
		}
		
		for(t_cnt ii=0; ii<n; ii++)
			renew(col[ii], k);

		if(t.flag&HAVE_COL)
			for(t_cnt j=0; j<n; j++)
				for(t_cnt g=0; g<col[0].len; g++)
					col[j].num[g]=t.col[j].num[g];
	}

	return *this;
}


CBinLongWord CBinLongMatrix::operator*(CBinLongWord& a)
{
	CBinLongWord res(k);
	rowtocol();
	for(t_cnt i=n-1; i>=0; i--)
		if(a.num[i/MOD]>>(i%MOD)&I){
			for(t_cnt j=0; j<col[0].len; j++)
				res.num[j]^=col[i].num[j];
		}
	return res;
}



//tensor multiplication
CBinLongMatrix CBinLongMatrix::operator^(CBinLongMatrix &b)
{
	CBinLongMatrix C(k*b.k, n*b.n);

	for(t_cnt i=0; i<k; i++)
		for(t_cnt j=0; j<b.k; j++)
			C.row[i*b.k+j]=row[i]^b.row[j];

	return C;
}


CBinLongMatrix CBinLongMatrix::operator^(CBinLongWord &b)
{
	CBinLongMatrix C(k, n*b.n);
	for(t_cnt i=0; i<k; i++)
		C.row[i]=row[i]^b;
	return C;
}


//multiplication of matrix
CBinLongMatrix CBinLongMatrix::operator*(CBinLongMatrix &b)
{
	CBinLongMatrix C(k, b.n);

	rowtocol();
	b.rowtocol();
	
		for(t_cnt j=b.n-1; j>=0; j--)
			for(t_cnt i=n-1; i>=0; i--)
				if(b.col[j].num[i/MOD]>>(i%MOD)&I)
					for(t_cnt y=0; y<col[0].len; y++)
						C.col[j].num[y]^=col[i].num[y];
	C.coltorow();

	return C;
}


CBinLongMatrix CBinLongMatrix::operator +(CBinLongMatrix& a)
{
	CBinLongMatrix c=*this;

	return c+=a;
}


CBinLongMatrix& CBinLongMatrix::operator ^=(CBinLongWord& a)
{
	return (*this=*this^a);
}


CBinLongMatrix& CBinLongMatrix::operator *=(CBinLongMatrix& a)
{
	return (*this=*this*a);
}


CBinLongMatrix& CBinLongMatrix::operator ^=(CBinLongMatrix& a)
{
	return (*this=*this^a);
}


CBinLongMatrix& CBinLongMatrix::operator +=(CBinLongMatrix& a)
{
	for(t_cnt i=0; i<k; i++)
		for(t_cnt j=0; j<row[0].len; j++)
			row[i].num[j]^=a.row[i].num[j];

	return *this;
}

/*
void CBinLongMatrix::trans()
{
	CBinLongMatrix tmatr(n, k, flag);
	for(t_cnt i=0; i<n; i++)
		for(t_cnt j=0; j<k; j++)
			((i-j-n+k>=0)?
			(tmatr.row[i].num|=(row[j].num&(I<<(n-i-1)))<<(i-j-n+k))
			:(tmatr.row[i].num|=(row[j].num&(I<<(n-i-1)))>>(j-i+n-k)));

		*this=tmatr;	
}

*/

void CBinLongMatrix::rowtocol()//first right col will become first row 
{
	if(!(flag & HAVE_COL))
		set_hcol();
	else
		for(t_cnt i=0; i<n; i++)
			for(t_cnt j=0; j<col[0].len; j++)
				col[i].num[j]=(t_src)0;
	
	for(t_cnt i=0; i<n; i++)
		for(t_cnt j=k-1; j>=0; j--)
			col[i].num[j/MOD]|=(((row[j].num[i/MOD]>>(i%MOD))&I)<<((k-1-j)%MOD));
	
}




void CBinLongMatrix::coltorow()
{
	for(t_cnt j=0; j<k; j++)
	{
		for(t_cnt x=0; x<row[0].len; x++)
			row[k-1-j].num[x]=(t_src)0;
		for(t_cnt i=0; i<n; i++)
			row[k-1-j].num[i/MOD]^=(((col[i].num[j/MOD]>>(j%MOD))&I)<<(i%MOD));
	}
}



t_res CBinLongMatrix::edin(char ch)
{
	CBinLongMatrix  tmp(k, n);
	for(t_cnt x=0; x<k; x++)
			tmp.row[x]=row[x];//temporary class
	
	t_len t=0,i=0;
	CBinLongWord check(n);

	while(i<k)
	{
		if(row[i].num[(n-t-1)/MOD]>>((n-t-1)%MOD)&I) //found 1
			{
				for(t_cnt h=i+1; h<k; h++)
					if(row[h].num[(n-t-1)/MOD]>>((n-t-1)%MOD)& I)
						for(t_cnt b=0; b<row[0].len; b++)
							row[h].num[b]^=row[i].num[b];
				
				check.num[(n-1-t)/MOD]^=(I<<((n-1-t)%MOD));				//check indicates those positions where 1 is(by putting in this position 1)
				t++;
				i++;
			}
	
		else
		{
			t_len h=i+1;
			while((h<k) && (!(row[h].num[(n-t-1)/MOD]>>((n-t-1)%MOD))&I))
			    h++;		
			if(h==k)t++;
			else
				for(t_cnt c=0; c<row[0].len; c++)
					row[i].num[c]^=row[h].num[c];
			
			if(t>=n)
			{			//not linear dependent case
				for(t_cnt x=0; x<k; x++)
					row[x]=tmp.row[x];
				return 0;
			}
		}
	}
//annulating above
		int val=k-2;
			for(i=0; i<n-1; i++)
				if(check.num[i/MOD]>>(i%MOD)&I)
				{
					for(t_cnt h=val; h>=0; h--)
					if((row[h].num[i/MOD]>>(i%MOD))&I)
						for(t_cnt f=0; f<row[0].len; f++)
							row[h].num[f]^=row[val+1].num[f];
					val--;
				}

//arranging by gathering single matrix to left/right

		rowtocol();
		t_len m=0; 
		if(ch=='l') //by default gathering single matrix to left
		{	
			for(t_cnt c=0; c<n; c++)
				if(check[(n-1-c)/MOD]>>((n-1-c)%MOD)&I)
				{
					CBinLongWord tt=col[n-1-c];
					col[n-1-c]=col[n-1-m];
					col[n-1-m]=tt;
					m++;
				}
		}
		else if(ch=='r') //when ch='r' gathering single matrix to right
		{	
			for(t_cnt c=0; c<n; c++)
				if(check.num[c/MOD]>>(c%MOD)&I)
				{
					CBinLongWord tt=col[c];
					col[c]=col[m];
					col[m]=tt;
					m++;
				}
		}

	coltorow();
	return 1;
}



CBinLongWord CBinLongMatrix::gaus()
{
	t_len t=0,i=0;
	CBinLongWord check(n);
	while(i<k){
		if((row[i].num[(n-t-1)/MOD]>>((n-t-1)%MOD)) &I) //found 1
			{
				for(t_cnt h=i+1; h<k; h++)
					if((row[h].num[(n-t-1)/MOD]>>((n-t-1)%MOD))&I)
						for(t_cnt b=0; b<row[0].len; b++)
							row[h].num[b]^=row[i].num[b]; //adding string if 1
				
				check.num[(n-1-t)/MOD]^=(I<<((n-1-t)%MOD));			//check indicates those positions where 1 is(by putting in this position 1)
				t++;
				i++;
			}
	
		else
		{
			t_len h=i+1;
			while((h<k) && (!(row[h].num[(n-t-1)/MOD]>>((n-t-1)%MOD))&I))
			    h++;		
			if(h==k)t++;
			else{
				for(t_cnt c=0; c<row[0].len; c++)
					row[i].num[c]^=row[h].num[c];
			}
			if(t>=n)
				return check;
		}
	}

	return check;
}


void CBinLongMatrix::cyclic_shift(t_len y, char where)
{
	for(t_cnt i=0; i<k; i++)
		row[i].cyclic_shift(y, where);
}


/*


void CBinLongMatrix::mixer()
{
	if(!(flag & SERIES))
	{
		series=new t_tab[n];

		for(t_cnt di=0; di<n; di++)
			series[di]=t_tab(di);

		flag^=SERIES;
	}
	//finding
	t_len i=n-1;
	while((series[i]<series[i-1]) && i>0)i--;

	t_len g=i-1; 
	if(g!=-1)
	{
		char temp=series[g];
		t_len h=n-1;

		while((h>g) && (temp>series[h]))
			h--;
		series[g]=series[h];
		series[h]=temp;
	
		char tmp;
		//resorting
		for(t_cnt m=g+1; m<(n+g-1)/2+1; m++)
		{
			tmp=series[n-m+g]; // just swapping
			series[n-m+g]=series[m];
			series[m]=tmp;
		}

		
		//series[n-h+g]=temp;
		
	}

 CBinLongWord* temp=new CBinLongWord[n];
 rowtocol();

 for(t_cnt l=0; l<n; l++)
	temp[l].num=col[series[l]].num;

  for(t_cnt ll=0; ll<n; ll++)
   col[ll].num=temp[ll].num;

 coltorow();
 delete[] temp;
 
}



void showtab(t_tab* ch, t_len n)
{
	for(t_cnt i=0; i<n; i++)
	 cout<<char(*(ch+i)+48);
}
 */

void CBinLongMatrix::set_col()
{
	flag^=COL^ROW;
}


void CBinLongMatrix::set_hcol()
{
	flag^=HAVE_COL;
}


void CBinLongMatrix::set_row()
{
	flag^=COL^ROW;
}


void CBinLongMatrix::set_base(int i){base=i;}


/*
t_src CBinLongMatrix::gaus1(){

    t_len main_var = 0 ;
    
    for( t_cnt i=0; i<k; i++ ){
        for( t_cnt j=i; j<n; ){
            if( row[i].is_set(j) ){
                main_var|=I<<j ;
                for( t_cnt t=i+1; t<k; t++ ){
                    if( row[t].is_set(j) )
                        row[t].num^=row[i].num ;       
                }
                break ;
            }
            else{
                t_cnt t=i+1;
                for( ; t<k; t++ ){
                    if( row[t].is_set(j) ){
                        row[i].num^=row[t].num ;    
                        main_var|=I<<j ;
                        break ;
                    }
                }
                if( t==k ) j++ ;
            }
        }
    }
return main_var ;                                
};

CBinLongWord CBinLongMatrix::gaus2(){
	CBinLongWord main_var(n);
	
	for( t_cnt i=0; i<k; i++ ){
		for( t_cnt j=i; j<n; ){
			if( row[i].is_set(j) ){
				main_var.num|=I<<j ;
				for( t_cnt t=i+1; t<k; t++ ){
					if( row[t].is_set(j) )
						row[t].num^=row[i].num ;       
				}
				break ;
			}
			else{
				t_cnt t=i+1;
				for( ; t<k; t++ ){
					if( row[t].is_set(j) ){
						row[i].num^=row[t].num ;    
						main_var.num|=I<<j ;
						break ;
					}
				}
				if( t==k ) j++ ;
			}
		}
	}
	return main_var ;
}

*/
void add_mat(CBinLongMatrix& a, CBinLongMatrix& b, CBinLongMatrix& c)
{
	for(t_cnt i=0; i<c.k; i++)
		for(t_cnt j=0; j<c.row[0].len; j++)
			a.row[i].num[j]=c.row[i].num[j]^b.row[i].num[j];
}

void mul_mat(CBinLongMatrix& a, CBinLongMatrix& c, CBinLongMatrix& b)
{

	c.rowtocol();
	b.rowtocol();
	
		for(t_cnt j=b.n-1; j>=0; j--)
			for(t_cnt i=c.n-1; i>=0; i--)
				if(b.col[j].num[i/MOD]>>(i%MOD)&I)
					for(t_cnt y=0; y<c.col[0].len; y++)
						a.col[j].num[y]^=c.col[i].num[y];
	a.coltorow();
}


void mul_vec(CBinLongWord& a, CBinLongMatrix& c, CBinLongWord& b)
{
	c.rowtocol();

	for(t_cnt i=c.n-1; i>=0; i--)
		if(b.num[i/MOD]>>(i%MOD)&I){
			for(t_cnt j=0; j<c.col[0].len; j++)
				a.num[j]^=c.col[i].num[j];
		}
}


void tmul_mat(CBinLongMatrix& a, CBinLongMatrix& c, CBinLongMatrix& b)
{
	for(t_cnt i=0; i<c.k; i++)
		for(t_cnt j=0; j<b.k; j++)
			a.row[i*b.k+j]=c.row[i]^b.row[j];
}


void tmul_vec(CBinLongMatrix& a, CBinLongMatrix& c, CBinLongWord& b)
{
	for(t_cnt i=0; i<c.k; i++)
		a.row[i]=c.row[i]^b;
}
